/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: btree.c 36 2009-11-02 15:06:50Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <assert.h>

#include "function_prototypes.h"
#include "btree.h"
#include "btree_funcs.h"
#include "rbbtree_funcs.h"

/* Used to help clean up an btree. */
static void btree_destroy_helper (struct btree_node *, destroy_func *);

Btree * 
btree_create (comp_func *comp, BtreeType type)
{
  Btree *btree;

  /* Make the structure. */
  btree = malloc (sizeof (Btree));
  if (btree == NULL)
    {
      return NULL;
    }

  /* Start off fresh. */
  btree->root = NULL;
  btree->size = 0;
  btree->comp = comp;
  btree->type = type;

  return btree;
}

void 
btree_destroy (Btree *btree, destroy_func *dest)
{
  assert (btree != NULL);

  btree_destroy_helper (btree->root, dest);
  
  free (btree);

}

void * 
btree_insert (Btree *btree, void *data)
{
  struct btree_node *cur, *prev, *nnode;
  int cmp;

  cmp = 0;

  assert (btree != NULL);

  cur = btree->root;
  prev = NULL;
  nnode = NULL;

  /* Find the place of insertion. */
  while (cur != NULL)
    {
      cmp = (*btree->comp)(data, cur->data);

      /* We already have that item. Return what is in the tree. */
      if (cmp == 0)
	return (void *)cur->data;
      else if (cmp > 0)
	{
	  /* This one is bigger than cur. */
	  prev = cur;
	  cur = cur->right;
	}
      else
	{
	  /* This one is smaller than cur. */
	  prev = cur;
	  cur = cur->left;
	}
    }

  /* Create the new node based on the tree we are using. */
  switch (btree->type)
    {
    case BST:
      nnode = new_node (data, NULL, NULL);
      break;
    case RB:
      nnode = new_rbbtree_node (data, RBBTREE_RED, NULL, NULL);
      break;
    }

  if (nnode == NULL) 
    return NULL;

  nnode->parent = prev;

  /* Increase size. */
  btree->size++;

  /* Check for insertion at root. */
  if (prev == NULL)
    btree->root = nnode;
  /* Is the new node the parent's right? */
  else if (cmp > 0)
    prev->right = nnode;
  /* Must be left. */
  else
    prev->left = nnode;

  /* Balance the btree based on type. */
  switch (btree->type)
    {
    case BST:
      /* Do nothing. */
      break;
    case RB:
      rbbtree_insert_case1 (btree, nnode);
      break;
    }

  return (void *)data;
}

void * 
btree_find (Btree *btree, void *search)
{
  struct btree_node * found;

  assert (btree != NULL);

  found = probe (btree, search);

  if (found == NULL)
    return NULL;
  else
    return (void *)found->data;
}

void * 
btree_remove (Btree *btree, void *data)
{
  struct btree_node *cur;

  cur = probe (btree, data);

  /* Couldn't find it. */
  if (cur == NULL)
    return NULL;
  else
    return remove_node (btree, cur);
}

void 
btree_destroy_helper (struct btree_node *node, destroy_func *dest)
{
  if (node == NULL)
    return;

  /* We do this recursively. If we start using large sets, this could be
     optimized. */
  btree_destroy_helper (node->left, dest);
  btree_destroy_helper (node->right, dest);
  
  if (dest != NULL)
    (*dest) ((void *)node->data);

  free (node);
}

void 
btree_traverser_init (BtreeTraverser *trav, Btree *btree)
{
  assert (trav != NULL);
  assert (btree != NULL);

  trav->btree = btree;
  trav->cur = NULL;
}

void *
btree_traverser_first (BtreeTraverser *trav)
{
  struct btree_node *first;

  assert (trav != NULL);
  assert (trav->btree != NULL);

  first = find_min (trav->btree);

  trav->cur = first;

  if (first == NULL)
    return NULL;
  else
    return (void *) first->data;
}

void *
btree_traverser_last (BtreeTraverser *trav)
{
  struct btree_node *last;

  assert (trav != NULL);
  assert (trav->btree != NULL);

  last = find_max (trav->btree);

  trav->cur = last;

  if (last == NULL)
    return NULL;
  else
    return (void *) last->data;

}

void *
btree_traverser_next (BtreeTraverser *trav)
{
  assert (trav != NULL);
  
  /* We'll give back the 'first' to make traversal easier. */
  if (trav->cur == NULL) 

    {
      return btree_traverser_first (trav);
    }
  else if (trav->cur->right == NULL)
    {
      struct btree_node *parent, *child;
      child = trav->cur;
      parent = child->parent;

      /* We need to loop through until we find a parent that wouldn't
	 have been visited before this one (child == parent->left). */
      while (1)
	{
	  if (parent == NULL || child == parent->left)
	    {
	      trav->cur = parent;
	      if (trav->cur != NULL)
		return (void *)trav->cur->data;
	      else
		return NULL;
	    }	  
	  
	  child = parent;
	  parent = parent->parent;
	}
    }
  /* We can just find the left most item. */
  else
    {
      trav->cur = trav->cur->right;

      while (trav->cur->left != NULL)
        trav->cur = trav->cur->left;
      
      return (void *)trav->cur->data;
    }
}

void *
btree_traverser_prev (BtreeTraverser *trav)
{
  assert (trav != NULL);

  /* We'll give back the 'last' to make traversal easier. */
  if (trav->cur == NULL)
    {
      return btree_traverser_last (trav);
    }
  else if (trav->cur->left == NULL)
    {
      struct btree_node *parent, *child;
      child = trav->cur;
      parent = child->parent;

      /* We need to loop through until we find a parent that wouldn't
	 have been visited before this one (child == parent->right). */
      while (1)
	{
	  if (parent == NULL || child == parent->right)
	    {
	      trav->cur = parent;
	      if (trav->cur != NULL)
		return (void *)trav->cur->data;
	      else
		return NULL;
	    }	  
	  
	  child = parent;
	  parent = parent->parent;
	}
    }
  /* We can just find the right most item. */
  else
    {
      trav->cur = trav->cur->left;

      while (trav->cur->right != NULL)
        trav->cur = trav->cur->right;
      
      return (void *)trav->cur->data;
    }
}

void * 
btree_traverser_cur (BtreeTraverser *trav)
{
  assert (trav != NULL);

  if (trav->cur == NULL)
    return NULL;
  else
    return (void *)trav->cur->data;
}


